<!doctype html>
<html lang="zh-CN">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>岛屿数量 - 算法详解</title>
    <link rel="stylesheet" href="https://cdn.staticfile.org/font-awesome/6.4.0/css/all.min.css">
    <link rel="stylesheet" href="https://cdn.staticfile.org/tailwindcss/2.2.19/tailwind.min.css">
    <link href="https://fonts.googleapis.com/css2?family=Noto+Serif+SC:wght@400;500;600;700&family=Noto+Sans+SC:wght@300;400;500;700&display=swap" rel="stylesheet">
    <script src="https://cdn.jsdelivr.net/npm/mermaid@latest/dist/mermaid.min.js"></script>
    <style>
        body {
            font-family: 'Noto Sans SC', Tahoma, Arial, Roboto, "Droid Sans", "Helvetica Neue", "Droid Sans Fallback", "Heiti SC", "Hiragino Sans GB", Simsun, sans-serif;
            background: linear-gradient(135deg, #f5f7fa 0%, #c3cfe2 100%);
            min-height: 100vh;
        }
        
        .hero-gradient {
            background: linear-gradient(135deg, #667eea 0%, #764ba2 100%);
        }
        
        .card-hover {
            transition: all 0.3s ease;
            border: 2px solid transparent;
        }
        
        .card-hover:hover {
            transform: translateY(-5px);
            box-shadow: 0 20px 40px rgba(0,0,0,0.1);
            border-color: #667eea;
        }
        
        .code-container {
            background: #1e1e1e;
            border-radius: 12px;
            overflow: hidden;
            box-shadow: 0 10px 30px rgba(0,0,0,0.2);
        }
        
        .code-header {
            background: #2d2d2d;
            padding: 10px 20px;
            display: flex;
            align-items: center;
            gap: 8px;
        }
        
        .code-dot {
            width: 12px;
            height: 12px;
            border-radius: 50%;
        }
        
        pre {
            margin: 0;
            padding: 20px;
            overflow-x: auto;
            color: #d4d4d4;
            font-family: 'Consolas', 'Monaco', monospace;
            font-size: 14px;
            line-height: 1.6;
        }
        
        .algorithm-badge {
            background: linear-gradient(135deg, #667eea 0%, #764ba2 100%);
            color: white;
            padding: 4px 12px;
            border-radius: 20px;
            font-size: 14px;
            display: inline-block;
            margin: 4px;
            transition: transform 0.2s ease;
        }
        
        .algorithm-badge:hover {
            transform: scale(1.05);
        }
        
        .grid-cell {
            width: 40px;
            height: 40px;
            display: flex;
            align-items: center;
            justify-content: center;
            font-weight: bold;
            border-radius: 4px;
            transition: all 0.3s ease;
        }
        
        .land {
            background: #10b981;
            color: white;
        }
        
        .water {
            background: #3b82f6;
            color: white;
        }
        
        .visited {
            background: #6b7280;
            color: white;
        }
        
        .mermaid {
            display: flex;
            justify-content: center;
            margin: 2rem 0;
        }
        
        .drop-cap {
            float: left;
            font-size: 4rem;
            line-height: 1;
            font-weight: 700;
            margin-right: 0.5rem;
            color: #667eea;
            font-family: 'Noto Serif SC', serif;
        }
        
        .highlight-text {
            background: linear-gradient(120deg, #f093fb 0%, #f5576c 100%);
            -webkit-background-clip: text;
            -webkit-text-fill-color: transparent;
            font-weight: 600;
        }
    </style>
</head>
<body>
    <!-- Hero Section -->
    <section class="hero-gradient text-white py-20">
        <div class="container mx-auto px-6 text-center">
            <h1 class="text-5xl md:text-6xl font-bold mb-6 animate-pulse">
                <i class="fas fa-island mr-4"></i>岛屿数量
            </h1>
            <p class="text-xl md:text-2xl mb-8 opacity-90">探索二维网格中的陆地连通性问题</p>
            <div class="flex justify-center gap-4 flex-wrap">
                <span class="algorithm-badge"><i class="fas fa-search mr-2"></i>深度优先搜索</span>
                <span class="algorithm-badge"><i class="fas fa-layer-group mr-2"></i>广度优先搜索</span>
                <span class="algorithm-badge"><i class="fas fa-project-diagram mr-2"></i>并查集</span>
            </div>
        </div>
    </section>

    <!-- Main Content -->
    <main class="container mx-auto px-6 py-12">
        <!-- Problem Description Card -->
        <div class="bg-white rounded-2xl shadow-xl p-8 mb-8 card-hover">
            <h2 class="text-3xl font-bold mb-6 text-gray-800">
                <i class="fas fa-book-open mr-3 text-purple-600"></i>题目描述
            </h2>
            <div class="prose prose-lg max-w-none">
                <p class="text-gray-700 leading-relaxed">
                    <span class="drop-cap">给</span>定一个由 '1'（陆地）和 '0'（水）组成的二维网格地图，计算岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。网格的四个边均被水包围。
                </p>
            </div>
            
            <!-- Visual Example -->
            <div class="mt-8 bg-gray-50 rounded-xl p-6">
                <h3 class="text-xl font-semibold mb-4 text-gray-800">
                    <i class="fas fa-map mr-2 text-blue-600"></i>示例地图
                </h3>
                <div class="grid grid-cols-5 gap-2 max-w-xs mx-auto">
                    <div class="grid-cell land">1</div>
                    <div class="grid-cell land">1</div>
                    <div class="grid-cell land">1</div>
                    <div class="grid-cell land">1</div>
                    <div class="grid-cell water">0</div>
                    <div class="grid-cell land">1</div>
                    <div class="grid-cell land">1</div>
                    <div class="grid-cell water">0</div>
                    <div class="grid-cell land">1</div>
                    <div class="grid-cell water">0</div>
                    <div class="grid-cell land">1</div>
                    <div class="grid-cell land">1</div>
                    <div class="grid-cell water">0</div>
                    <div class="grid-cell water">0</div>
                    <div class="grid-cell water">0</div>
                    <div class="grid-cell water">0</div>
                    <div class="grid-cell water">0</div>
                    <div class="grid-cell water">0</div>
                    <div class="grid-cell water">0</div>
                    <div class="grid-cell water">0</div>
                </div>
                <p class="text-center mt-4 text-gray-600">
                    <i class="fas fa-info-circle mr-2"></i>此地图包含 <span class="highlight-text">1 个岛屿</span>
                </p>
            </div>
        </div>

        <!-- Algorithm Analysis -->
        <div class="grid md:grid-cols-3 gap-6 mb-8">
            <!-- DFS Card -->
            <div class="bg-white rounded-2xl shadow-xl p-6 card-hover">
                <div class="text-center mb-4">
                    <i class="fas fa-search text-4xl text-purple-600"></i>
                </div>
                <h3 class="text-xl font-bold mb-3 text-center">深度优先搜索 (DFS)</h3>
                <p class="text-gray-600 mb-4">遍历网格，遇到陆地时使用 DFS 将相连的陆地标记为已访问，计数岛屿数量。</p>
                <div class="bg-purple-50 rounded-lg p-3">
                    <p class="text-sm"><i class="fas fa-clock mr-2 text-purple-600"></i>时间复杂度：O(m×n)</p>
                    <p class="text-sm mt-1"><i class="fas fa-memory mr-2 text-purple-600"></i>空间复杂度：O(m×n)</p>
                </div>
            </div>

            <!-- BFS Card -->
            <div class="bg-white rounded-2xl shadow-xl p-6 card-hover">
                <div class="text-center mb-4">
                    <i class="fas fa-layer-group text-4xl text-blue-600"></i>
                </div>
                <h3 class="text-xl font-bold mb-3 text-center">广度优先搜索 (BFS)</h3>
                <p class="text-gray-600 mb-4">类似 DFS，但使用队列代替递归，逐层扩展搜索范围。</p>
                <div class="bg-blue-50 rounded-lg p-3">
                    <p class="text-sm"><i class="fas fa-clock mr-2 text-blue-600"></i>时间复杂度：O(m×n)</p>
                    <p class="text-sm mt-1"><i class="fas fa-memory mr-2 text-blue-600"></i>空间复杂度：O(min(m,n))</p>
                </div>
            </div>

            <!-- Union Find Card -->
            <div class="bg-white rounded-2xl shadow-xl p-6 card-hover">
                <div class="text-center mb-4">
                    <i class="fas fa-project-diagram text-4xl text-green-600"></i>
                </div>
                <h3 class="text-xl font-bold mb-3 text-center">并查集</h3>
                <p class="text-gray-600 mb-4">将相邻陆地合并为一个集合，最终统计独立集合的数量。</p>
                <div class="bg-green-50 rounded-lg p-3">
                    <p class="text-sm"><i class="fas fa-clock mr-2 text-green-600"></i>时间复杂度：O(m×n)</p>
                    <p class="text-sm mt-1"><i class="fas fa-memory mr-2 text-green-600"></i>空间复杂度：O(m×n)</p>
                </div>
            </div>
        </div>

        <!-- Algorithm Flow Diagram -->
        <div class="bg-white rounded-2xl shadow-xl p-8 mb-8">
            <h2 class="text-3xl font-bold mb-6 text-gray-800">
                <i class="fas fa-sitemap mr-3 text-indigo-600"></i>算法流程图
            </h2>
            <div class="mermaid">
                graph TD
                    A[开始遍历网格] --> B{当前格子是陆地?}
                    B -->|是| C[标记为已访问]
                    B -->|否| D[继续下一个格子]
                    C --> E[DFS/BFS搜索相邻格子]
                    E --> F[标记所有相连陆地]
                    F --> G[岛屿计数+1]
                    G --> D
                    D --> H{遍历完成?}
                    H -->|否| B
                    H -->|是| I[返回岛屿数量]
                    
                    style A fill:#667eea,stroke:#fff,stroke-width:2px,color:#fff
                    style I fill:#10b981,stroke:#fff,stroke-width:2px,color:#fff
                    style C fill:#f59e0b,stroke:#fff,stroke-width:2px,color:#fff
                    style G fill:#ef4444,stroke:#fff,stroke-width:2px,color:#fff
            </div>
        </div>

        <!-- Code Implementation -->
        <div class="bg-white rounded-2xl shadow-xl overflow-hidden mb-8">
            <h2 class="text-3xl font-bold p-8 pb-4 text-gray-800">
                <i class="fas fa-code mr-3 text-green-600"></i>代码实现
            </h2>
            <div class="px-8 pb-8">
                <div class="code-container">
                    <div class="code-header">
                        <div class="code-dot bg-red-500"></div>
                        <div class="code-dot bg-yellow-500"></div>
                        <div class="code-dot bg-green-500"></div>
                        <span class="ml-4 text-gray-400">NumIslands.java</span>
                    </div>
                    <pre><code>public int numIslands(char[][] grid) {
    // 边界检查
    if (grid == null || grid.length == 0 || grid[0].length == 0) {
        return 0;
    }
    
    // 获取网格的行数和列数
    int rows = grid.length;
    int cols = grid[0].length;
    
    // 岛屿计数
    int count = 0;
    
    // 遍历整个网格
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            // 如果当前单元格是陆地（'1'）
            if (grid[i][j] == '1') {
                // 使用DFS将与当前陆地相连的所有陆地标记为已访问
                dfs(grid, i, j);
                // 找到一个新的岛屿，计数加1
                count++;
            }
        }
    }
    
    // 返回岛屿总数
    return count;
}

/**
 * 深度优先搜索，将与当前陆地相连的所有